1. Field of the Invention
This invention relates to an apparatus and method for determining a number of digits leading a particular digit in a data input signal.
2. Description of the Related Art
An apparatus and method for determining a number of bits leading a particular bit ("leading bit indicator" when considering a binary digit apparatus) pertains to a device used to determine a number of particular count bits in a binary data signal that lead or precede a non-count bit. Each binary digit ("bit") has a value, either a one or a zero. If it is desirable to count leading bits having a value of zero, for example, then a count bit would have a value of zero and a non-count bit would have a value of one. A leading bit indicator, or leading zero indicator for the previous example, would provide an indication of the number of count bits, in a data signal containing multiple bits, that precede a non-count bit. Those count bits that lead a non-count bit in a data signal are the most significant bits. For example, each bit in a binary data signal has ones usually represented by positive voltage levels (e.g. +5 V) and/or zeros usually represented by a common ground voltage level (i.e. 0 V). Assuming a binary data signal contains 16 bits, a 16 bit binary Leading Zero Indicator would count the number of leading zeros (where zeros constitute a count bit) by determining the number of zeros that lead or precede the first one (where ones constitute a non-count bit) in the 16 bit data input signal. (Note: in the absence of a one, the number of leading zeros would equal the number of bits in the data input signal). In a numerical example, if a 16 bit binary Leading Zero Counter had a 16 bit binary data input signal such as 0000 0000 0011 0111.sub.2, the Leading Zero Indicator would contain a 1010.sub.2 output which represents the number of leading zeros.
Leading bit indicators are particularly useful when incorporated in floating point units. Floating point units perform floating point computations which play an important role in the realm of microprocessors. Leading zero bit counters have been particularly useful in assisting floating point units to meet ANSI/IEEE Std. 754-1985 ("IEEE Std.") for binary floating point arithmetic.
A floating point number consists of a significand, also known as a fraction or mantissa, and an exponent, which is usually (but not always) a power of 2. The exponent and significand may both vary in length depending on the range and precision desired. Signed numbers can be stored in either sign and magnitude form or by using a complement notation. (A floating point unit number may also consist of other specialty bits positioned before and/or after and/or between the significand and the exponent).
The IEEE Std. mandates representing the value of a floating point number in a normalized form i.e. as (-1).sup.sign 2.sup.exponent+bias (significand) where the bias is chosen so that exponent + bias will be a positive value. (Note: the IEEE Std. provides for a denormalized number which is a non-zero number containing leading zeros and whose exponent plus bias has a reserved value usually equal to zero). Therefore, to comply with IEEE Std. the significand and the exponent must be adjusted accordingly in order to eliminate leading zeros. Assuming that the floating point unit is designed to process binary numbers, after performing an arithmetic operation on two binary numbers the result often contains leading zeros. Unless the exponent has a minimum value, a result containing leading zeros fails to comply with the IEEE Std.
For example, if a 32 bit number has a 23 bit significand consisting of bits 0.0000001000011010101110.sub.2, an exponent consisting of 01001011.sub.2, and a sign bit of 0.sub.2, the significand would be in an unacceptable format because the exponent is greater than the minimum exponent and zeros lead the first one in the significand. In order to put the significand into an acceptable or normalized format, the number of leading zeros should be counted and subtracted from the exponent. The significand should also be shifted to the left a number of times equal to the number of leading zeros which will place the first 1 bit in the most significant bit place. After following this procedure, a number meeting the IEEE Std. is obtained. Using the above 32 bit number, the number of leading zeros equals 0111.sub.2 Therefore, the significand is shifted to the left 0111.sub.2 times, and 0111.sub.2 is subtracted from the exponent. The example significand and exponent would now look like 1.0000110101011100000000 and 01000100.sub.2 which meets the IEEE Std.
The model 29050 Microprocessor, available from Advanced Micro Devices of Sunnyvale, Calif., contains a 56 bit leading bit indicator. FIG. 1 illustrates a high level block diagram of the leading one bit indicator found in the AMD 29050. (Note: a leading one indicator may easily be converted to determine a number of leading zeros by inverting each of the data input signal bits prior to its reception by the leading one indicator). Referring to FIG. 1, the AMD 29050 56 bit counter receives a 56 bit number with the last bit, bit 0, being the least significant bit and the first bit, bit 55, being the most significant bit. The 8 bit counter logic 112 receives the most significant group of bits 48-55, 8 bit counter logic 110 receives the second most significant group of bits 40-47, 8 bit counter logic 108 receives the third most significant group of bits 40-47, 8 bit counter logic 108 receives the fourth most significant group of bits 32-39, 8 bit counter logic 106 receives the fifth most significant group of bits 24-21, 8 bit counter logic 104 receives the sixth most significant group of bits 16-23, 8 bit counter logic 102 receives the seventh most significant group of bits 8-15, and 8 bit counter logic 100 receives least significant group of bits 0-7. Each 8 bit counter logic provides two outputs. The first output is a 3 bit output representing the number of leading ones in the 8 bit data input signal of the 8 bit counter logic. The second output of the 8 bit counter logic is a 2 bit signal representing the presence of a zero in the least significant 4 bits and the presence of a zero in the most significant 4 bits.
The 56 bit counter logic 122 receives the output of 8 bit counter logic 100. The 16 bit counter logic 114 receives the outputs of 8 bit counter logic 102 and 104. The 56 bit counter logic 122 receives two outputs from 16 bit counter logic 114. The first output of 16 bit counter logic 114 is a 4 bit number representing the number of leading ones in the data input signal to 16 bit counter logic 114. The second output is a 2 bit number that represents the presence or the absence of a zero in bits 8-23. Sixteen bit counter logic 114 first determines the presence of a zero in the most significant 8 bits 16-23. If a zero is present, the circuit determines only the number of zeros in the most significant 8 bits. If the most significant 8 bits contained all ones, the output would correspond to the 8 ones in the most significant 8 bits plus the number of ones in the least significant 8 bits. The output is then received by the 56 bit counter logic 122.
Sixteen bit counter logic 116 functions similarly to 16 bit counter logic 114 except that 16 bit counter logic 116 operates on bits 24-39 and 16 bit counter logic 118 operates on bits 48-55. Sixteen bit counter logic 116 and 16 bit counter logic 118 have outputs that are received by 32 bit counter logic 120. Thirty-two bit counter logic 120 determines the number of ones in the two 16 bit counter logics 116 and 118. If the most significant 16 bits, bits 40-55, contain a zero, the output of 32 bit counter logic will represent the number of ones present in bits 40-55. If bits 40-55 contain all ones, the output of 32 bit counter logic 120 will reflect the number of ones present in bits 24-55. Thirty-two bit counter logic 120 has a second output indicating whether or not a zero is present in bits 40-55 and whether or not a zero is present in bits 24-39.
Fifty-six bit counter logic 122 contains the final output which represents the number of leading ones in the original 56 bit data input signal. Fifty-six bit counter logic 122 operates by detecting the presence of a zero in the most significant 32 bits. If a zero is detected, the number of ones received from 32 bit counter logic 120 are provided to an output. This result represents the correct number of leading ones in the original 56 bit data input signal. If the most significant 32 bits contain all ones, 56 bit counter logic 122 then analyzes the next 16 bits, bits 8-23, and detects the presence of a zero. If a zero is present, the output of 56 bit counter logic 122 represents the most significant 32 bits containing ones exclusively and the number of leading ones in the next 16 bits, bits 8-23. The 56 bit counter logic 122 subsequently analyzes the 8 bit counter logic 100 output only if the most significant 48 bits contained all ones. If the most significant 48 bits contained all ones, the output of 56 bit counter logic 122 would reflect the number of leading ones in the most significant 48 bits containing ones exclusively and the number of leading ones in the least significant 8 bits. Fifty-six bit counter logic 122 has a second output that represents the presence of a zero anywhere in the original 56 bit data input signal.
A disadvantage of the discussed prior art is the complex implementation of multiple stages necessary to determine the number of leading count bits present in a data input signal. Further, complex implementation results in a slower device speed due to propagation delays from a larger number of logic stages.